Traditionally, the input to a three-dimensional graphics system is a scene consisting of geometric primitives composed of different materials and a set of lights. Based on this input specification, the rendering system computes and outputs an image. Recently, a new approach to rendering has emerged which is known as image-based rendering. Image-based rendering systems generate different views of an environment from a set of pre-acquired imagery.
There are several advantages to the image-based rendering approach. First, the display algorithms for image-based rendering require modest computational resources and are thus suitable for real-time implementation on workstations and personal computers. Second, the cost of interactively viewing the scene is independent of the scene complexity. Even with the best algorithms and fastest hardware, it often takes minutes or hours using existing systems to generate images with the visual richness required for many applications. Third, the source of the pre-acquired images can be from a real or virtual environment (i.e. from digitized photographs or from rendered models), or from a combination of the two.
The forerunner to these techniques is the use of environment maps to capture the incoming light in a texture map. See, e.g., J. F. Blinn & M. E. Newell, "Texture and Reflection in Computer Generated Images," CACM, Vol. 19, No. 10, October 1976, pp. 542-47; N. Greene, "Environment Mapping and Other Applications of World Projections," IEEE Computer Graphics and Applications, Vol. 6, No. 11, November 1986, pp. 21-29. An environment map records the incident light arriving from all directions at a point. The original use of environmental maps was to efficiently approximate reflections of the environment on a surface. However, environment maps also may be used to quickly display any outward looking view of the environment from a fixed location but at a variable orientation. For example, this is the basis of the Apple QuickTime VR system. See S. E. Chen, "QuickTime VR--An Image-Based Approach to Virtual Environment Navigation," Proc. SIGGRAPH '95 (Los Angeles, Calif., Aug. 6-11, 1995), Computer Graphics Proceedings, Annual Conference Series, 1995, ACM SIGGRAPH, pp. 29-38. In this system environment, maps are created at key locations in the scene. The user is able to navigate discretely from location to location, and while at each location continuously change the viewing direction.
The major limitation of rendering systems based on environment maps is that the viewpoint is fixed. One way to relax this fixed position constraint is to use view interpolation. See S. E. Chen & L. Williams, "View Interpolation for Image Synthesis," Proc. SIGGRAPH '93 (Anaheim, Calif., Aug. 1-6, 1993) Computer Graphics Proceedings, Annual Conference Series, 1993, ACM SIGGRAPH, pp. 279-88; N. Green and M. Kass, "Approximating Visibility with Environment Maps, Apple Technical Report no. 41, November 1994; H. Fuchs et al., "Virtual Space Teleconferencing Using a Sea of Cameras," Proc. First International Conference on Medical Robotics and Computer Assisted Surgery, 1994, pp. 161-67; L. McMillan & G. Bishop, "Head-Tracked Stereoscopic Display Using Image Warping," Stereoscopic Displays and Virtual Reality Systems II, Proc. SPIE, Vol. 240, S. Fisher, J. Merritt, B. Bolas eds. 1995, pp. 21-30; L. McMillan & G. Bishop, Plenoptic Modeling: An Image-Based Rendering System, Proc. SIGGRAPH '95 (Los Angeles, Calif., Aug. 6-11, 1995) Computer Graphics Proceedings, Annual Conference Series, 1995, ACM SIGGRAPH, pp. 39-46 (hereinafter "McMillan, Plenoptic Modeling"); P. J. Narayana, "Virtualized Reality: Concepts and Early Results," Proc. IEEE Workshop on the Representation of Visual Scenes, IEEE, 1995. Most of these methods require a depth value for each pixel in the environment map, which is easily provided if the environment maps are synthetic images. Given the depth value, it is possible to reproject points in the environment map from different vantage points to warp between multiple images. The key challenge in this warping approach is to "fill in the gaps" when previously occluded areas become visible.
Another approach to interpolating between acquired images is to find corresponding points in the two. See S. Laveau & O. D. Faugeras, "3-D Scene Representation as a Collection of Images and Fundamental Matrices," INRIA Technical Report No. 2205, 1994; McMillan, Plenoptic Modeling"; S. Seitz & C. Dyer, "Physically-Valid View Synthesis by Image Interpolation," Proc. IEEE Workshop on the Representation of Visual Scenes, IEEE, 1995. If the positions of the cameras are known, this is equivalent to finding the depth values of the corresponding points. Automatically finding correspondence between pairs of images is the classic problem of stereo vision; unfortunately, although many algorithms exist, these algorithms are fairly fragile and may not always find the correct correspondences.
An abstract representation of light that is related to the present invention is epipolar volumes. See R. Bolles et al, "Epipolar-Plane Image Analysis: An Approach to Determining Structure from Motion," International Journal of Computer Vision, Vol. 1, No. 1, 1987, pp. 7-55. An epipolar volume is formed of an array of images created by translating a camera in equal increments in a single direction. Such a representation has been used recently to perform view interpolation. Katayama et al. "Viewpoint-Dependent Stereoscopic Display Using Interpolation of Multiviewpoint Images," Stereoscopic Displays and Virtual Reality Systems II, Proc. SPIE, Vol. 2409, S. Fisher, J. Merrit, B. Bolas eds. 1995, pp. 11-20.
Another related representation is the horizontal-parallax-only holographic stereogram. S. Benton, "Survey of Holographic Stereograms," Processing and Display of Three-Dimensional Data, Proc. SPIE, Vol. 367, 1983. A holographic stereogram is formed by exposing a piece of film to an array of images captured by a camera moving sideways. Halle has discussed how to set the camera aperture to properly acquire images for holographic stereograms. M. Halle, "Holographic Stereograms as Discrete Imaging Systems," Practical Holography, Proc. SPIE, Vol. 2176, Febuary 1994. Gavin Miller has also recognized the potential synergy between true three-dimensional display technologies and computer graphics algorithms. G. Miller, "Volumetric Hyper-Reality: A Computer Graphics Holy Grail for the 21st Century?" Proc. Graphics Interface '95, W. Davis and P. Prusinkiewicz eds., Canadian Information Processing Society, 1995, pp. 56-64.